เฉลิมชัย เกิดเมื่อวันที่ 2 สิงหาคม พ.ศ. 2496 เป็นบุตรของ พ.ท.ยอดชัย กับนางบัวกลีบ มัจฉากล่ำ จบการศึกษาระดับ ม.ศ.4(ปวช.)ที่โรงเรียนช่างกลนนทบุรี แผนกช่างไฟฟ้า และเข้าศึกษาต่อระดับ ปวส.ที่วิทยาลัยเทคนิคกรุงเทพ แผนกเทคนิคอุตสาหกรรม ระหว่างที่เป็นนักเรียนอาชีวะ เกิดเหตุการณ์ 6 ตุลา ในปี พ.ศ. 2519 เขาถูกชักชวนจากพลตรี สุตสาย หัสดิน ให้เข้าร่วมขบวนการกระทิงแดง หลังเสร็จสิ้นภารกิจ นายเฉลิมชัยได้เข้าทำงานเป็นลูกจ้างชั่วคราวในกองอำนวยการรักษาความมั่นคงภายใน (กอ.รมน.) และต่อมานายเฉลิมชัยเข้าสอบบรรจุเป็นทหารได้ ติดยศว่าที่ร้อยตรี ประจำศูนย์รักษาความปลอดภัย กองบัญชาการทหารสูงสุด

เฉลิมชัย รับราชการจนในปี พ.ศ. 2531 ได้เลื่อนยศเป็น "พันตรี"